package arithmetic.demo9;


import  java.util.*;


/**
 * 题目： 链表_重排链表
 */
class ListNode {
    int val;
    arithmetic.demo9.ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, arithmetic.demo9.ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode reorderList(ListNode head) {
        if(head.next == null || head.next.next == null) {
            return head;
        }

        // 先找中间节点
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null ) {
            fast = fast.next.next;
            slow = slow.next;
        }


        ListNode cur = slow.next;
        ListNode ncur = cur;



        // 头插法逆置
        while(ncur != null) {
            ncur = ncur.next;
            cur.next = slow;
            slow = cur;
            cur = ncur;
        }




        // 开始加入
        ListNode  left = head, right = slow;
        ListNode newHead = new ListNode();
        ListNode ret = newHead;


        // 开始连接
        while(left != right && left.next != right) {
            ret.next = left;
            left = left.next;
            ret = ret.next;
            ret.next = right;
            right = right.next;
            ret = ret.next;
            if(left.next == right) {
                ret.next = left ;
                ret = ret.next;
                ret.next = right;
            }
        }

        ret.next.next = null;

        ListNode node = newHead.next;
        return  node;

    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode cur =head;
        for (int i = 2; i < 4; i++) {
            ListNode node = new ListNode(i);
            cur.next = node;
             cur = cur.next;
        }

        Solution solution = new Solution();
       cur = solution.reorderList(head);

        while (cur!= null) {
            System.out.println(cur.val);
            cur = cur.next;
        }

    }
}


/**
 *  题目： 链表_重排链表
 */



class Solution1 {
    public ListNode reorderList(ListNode head) {
        if(head.next == null || head.next.next == null) {
            return head;
        }

        // 先找中间节点
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null ) {
            fast = fast.next.next;
            slow = slow.next;
        }







        ListNode newh = new ListNode();
        ListNode cur = slow.next;
        slow.next = null;


        while (cur != null) {
            ListNode next = cur.next;
            cur.next = newh.next;
            newh.next = cur;
            cur = next;
        }




        // 开始加入
        ListNode  left = head, right = newh.next;
        ListNode newHead = new ListNode();
        ListNode ret = newHead;



        // 开始连接
        while(left != null) {
            ret.next = left;
            left = left.next;
            ret = left;

            if(right != null) {
                ret.next = right;
                right = right.next;
                ret = right;
            }
        }


        ListNode node = newHead.next;
        return  node;

    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode cur =head;
        for (int i = 2; i < 6; i++) {
            ListNode node = new ListNode(i);
            cur.next = node;
            cur = cur.next;
        }

        Solution solution = new Solution();
        cur = solution.reorderList(head);

        while (cur!= null) {
            System.out.println(cur.val);
            cur = cur.next;
        }

    }
}



class Solution2 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int sum = 0;


        // 计算链表总数
        while(cur != null) {
            sum++;
            cur= cur.next;
        }




        cur = head;
        int count = sum / k;
        int i =0;

        ListNode begin =null;

//        用数组来存储
        ListNode[] begins = new ListNode[count+1];
        ListNode[] ends = new ListNode[count];
        while(count-- > 0) {
            int n = k;
            ListNode head2 = new ListNode();
            ListNode end = cur;
            while(n-- > 0) {
               ListNode next = cur.next;
                cur.next = head2.next;
                head2.next = cur;
                cur = next;
            }

            if(count + 1 == (sum / k)) {
                begin = head2.next;
            }



            ends[i] = end;
            begins[i++] = head2.next;
        }

        int j =0;
        for ( j = 0; j < ends.length; j++) {
            ends[j].next =  begins[j+1];
        }

        ends[j-1].next = cur;
        return begin;
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode cur =head;
        for (int i = 2; i < 10; i++) {
            ListNode node = new ListNode(i);
            cur.next = node;
            cur = cur.next;
        }

        Solution2 solution = new Solution2();
        cur = solution.reverseKGroup(head,3);

        while (cur!= null) {
            System.out.println(cur.val);
            cur = cur.next;
        }

    }
}


/**
 * 题目： 链表_合并k个升序链表
 */

class Solution3 {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if(n == 0) {
            return null;
        }


        // 优先级队列
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a,b)->{
            return a.val - b.val;
        });



        // 加入队列
        for(int i=0; i < n; i++) {
            // 如果为 null 就不加入队列
            if(lists[i] != null) {
                queue.add(lists[i]);
            }
        }

        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        // 更新队列
        while(!queue.isEmpty()) {
            // 弹出堆顶元素
            ListNode node = queue.poll();
            cur.next = node;
            cur = node;
            node = node.next;
            if(node != null) {
                queue.add(node);
            }
        }

        // 最终返回结果即可
        return newHead.next;


    }
}


/**
 * 题目： 链表_合并K个升序链表
 */
class Solution4 {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        return dfs(lists, 0, lists.length-1);
    }

    private ListNode dfs(ListNode[] lists, int left, int right) {
        if(left == right) {
            return lists[left];
        }

        // 递归出口
        if(left > right) {
            return null;
        }





        int mid = (right + left) / 2;
        // 开始得到两边节点
        ListNode node1 = dfs(lists,left , mid );
        ListNode node2 = dfs(lists, mid+1, right);


        if(node1 == null) {
            return node2;
        }

        if(node2 == null) {
            return node1;
        }

        ListNode leftNode = node1;
        ListNode rightNode = node2;

        ListNode newHead = new ListNode();
        ListNode cur = newHead;

        // 进行俩升序链表的合并
        while(leftNode != null && rightNode != null) {
            if(leftNode.val < rightNode.val) {
                cur.next  = leftNode;
                leftNode = leftNode.next;
                cur = cur.next;
            } else {
                cur.next = rightNode;
                rightNode = rightNode.next;
                cur = cur.next;
            }
        }


        // 假如左边链表 不为 null
        if(leftNode != null) {
            cur.next = leftNode;
        }

        // 右边链表 不为 null
        if(rightNode != null) {
            cur.next = rightNode;
        }


        // 最终返回虚拟节点的下一个节点
        return newHead.next;
    }


    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        n1.next = new ListNode(4);
        n1.next.next = new ListNode(5);


        ListNode n2 = new ListNode(1);
        n2.next = new ListNode(3);
        n2.next.next = new ListNode(4);


        ListNode n3= new ListNode(2);
        n3.next = new ListNode(6);

        ListNode[] listNodes = new ListNode[]{n1,n2,n3};


        Solution4 solution4 = new Solution4();
        solution4.mergeKLists(listNodes);




    }
}





